package 力扣日常刷题.木22一月.第14天0123;

/**
 * @author 帅小伙
 * @date 2022/1/23
 * @description
 * dp[i][0] 表示前 i 个数中长为偶数的子序列的最大交替和
 */
public class Demo57动态规划最大子序列交替和 {


    public long maxAlternatingSum(int[] nums) {
        int n = nums.length;
        long[][] dp = new long[n][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] - nums[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i - 1][0] + nums[i]);
        }
        return Math.max(dp[n-1][0],dp[n-1][1]);
    }
}
